% In our work, we reduce the problem of interpreting natural language queries to a
% constraint-solving problem as explained later on. 
In general, the
problem of Question Answering (Q\&A) from structured data can be formalized as
follows: given a structured query language $L$ and a user's question $q$, we define a mapping $q \mapsto R$ to a ranked list $R$ (results) 
of structured queries  $r_{\rm 1},r_{\rm 2},\ldots,r_{\rm n} \in L$, where
$r_{\rm i}$ represents the $i$-th highest scored interpretation of the user's
questions with respect to the data and metadata of the underlying structured
data source.
%
%Note, that 
We focus in this paper on multi-dimensional queries (structured queries) and
data warehouses (data sources), without restricting the generality of our
approach. A simple multi-dimensional query
(see~\cite{Giacometti:2009:RMQ:1617540.1617589} for a more detailed definition)
is usually represented by a number of dimensions (organized in hierarchies) or
their attributes, measures (aggregated KPIs with respect to the used dimensions
or attributes) and filters. It is executed on top of a physical or virtual
data cube (through an abtraction layer generating a mapping to SQL in our
case).
In addition, result modifiers (e.g. for sorting and 
truncation) can be added to a query.   
The interested reader might already look up 
the logical schema of the example data warehouse used
throughout this paper in figure~\ref{fig:data-schema}. 
%
An example question, $q$=``Top 5 middle-aged customers in my
city'', is shown in figure~\ref{fig:running-example}, while
listing~\ref{lst:structured-query-1} depicts an example result query $r \in R$
in SQL syntax.
%(we will later switch to a more conceptual notation, but we use
%here SQL because we assume that the majority of readers is more experienced
%with SQL than multi-dimensional query languages such as MDX). 
Note that the join paths in the example, 
the aggregation function {\footnotesize \verb|sum()|}, and the expression inside the
aggregation function representing the measure `revenue' are predefined
in the data warehouse metadata.
%
We also depict in figure~\ref{fig:running-example} intermediate steps to derive
the final structured query. Successive tokens that satisfy some constraints 
(e.g. `customers', which matches the name of an entity in the data 
warehouse metadata) are marked with dotted-line boxes. Inferred semantics 
(e.g. the filter for the age range) are drawn with solid-line rectangles.

In order to derive a structured query $r \in R$ from a given question $q$, we have to solve a series of problems, which form a kind of process and
which we detail in the following:\\
%
%\paragraph{(1) Information Extraction}
\textbf{(1) Information Extraction:} 
The first step in the processing is 
to derive lower-level semantics from the user's question. This is, data and
metadata of the underlying structured data source (i.e. domain terminology) 
have to be recognized (e.g. `customers' refers to the dimension
`customer' in the data warehouse schema). 
%In this stage precision and
% recall of the recognition algorithms influence the overall quality of the
% generated queries.
% Even though matching the question and domain terminology is not the main scope 
% of this paper, nevertheless we will give an overview of the technologies that
%  are currently used by our system in section~\ref{information-extraction}. 
%
To support more sophisticated queries (e.g. range queries) and 
go beyond keyword-like questions, we 
%have to 
allow administrators to define custom vocabulary (such as `middle-aged') and
more complex linguistic patterns, which simple example is `top 5'.
Such artifacts may export variables, such as the beginning and ending of the age range
for `middle-aged' or the expected number of objects for `top 5'. \\
%We will discuss our solution for defining
%linguistic patterns in section~\ref{information-extraction}. 
%
\textbf{(2) Normalization and Transformation:} In many cases, we cannot 
map the users' input directly to a structured query. For instance dates or
numbers may be expressed in different forms (e.g. `15000' as 
`15,000', `15k' or even `fifteen thousand'). The same holds 
true for custom vocabulary such as `middle-aged', which translates to 
a range on the `age' attribute of the dimension `customer' (see 
figure~\ref{fig:data-schema}). Therefore, we need a configurable mechanism
to translate input variables derived from linguistic patterns to variables
that conform with the query language $L$. Similarly, we require a mechanism 
to define variables for custom vocabulary (e.g. `middle-aged' defines 
a range starting at `$20$' and ending at `$30$'). \\
%
%The details on how 
%to configure normalization and transformation functions can be found 
%in section~\ref{information-extraction}.
%
\textbf{(3) Structural Constraints and Missing Artifacts:}
One of the most challenging problems is to generate valid structured queries  
(valid in the sense that $q \in L$ holds and that $q$ returns a 
-- maybe empty -- result). To go deeper into our example, 
a series of constraints need to be considered 
%in order 
to generate valid multi-dimensional queries in a next processing step, 
such as:\\
%\begin{itemize}
  $\bullet$ Artifacts used within a query have to occur in the same data 
  warehouse (if several ones are used).\\
  $\bullet$ A query contains at least one measure or dimension.\\
  $\bullet$ A query that contains two dimensions requires one or more 
  measures that connect these dimensions (see figure~\ref{fig:data-schema}),
  which implies that these dimensions relate to the same fact table.\\
  $\bullet$ Different interpretations for ambiguously recognized dimensions 
  (i.e. different matches covering the same text fragment in the user's 
  question) shall not be used within the same structured query because 
  it would change the aggregation level.
  %Using ambiguously recognized measures or filter terms for the same 
  %dimension is not an issue because they do not change the overall 
  %semantics.\\ 
  %Still a couple of special cases need to be considered, 
  %e.g., if a fragment of a query refers to a dimension or a filter
  %term.  
  \\
  $\bullet$ A sorting or truncation criteria (e.g. `top 5') requires 
  usually an assigned measure (note that several sortings 
  and truncations can be applied within one query, e.g. for a question
   like `Revenue for the top 5 cities and the top 10 resorts'). 
   If no measure for a sorting or truncation criteria 
   can be extracted from the question, the system has to propose 
   at least one measure, e.g. `revenue', as shown 
   in listing~\ref{lst:structured-query-1} for the missing 
  input `\emph{?1}' in figure~\ref{fig:running-example}. 
%\end{itemize}

%The examples above are an only an excerpt of the constraints that occur in 
%the domain of BI. 
Other constraints that occur in the BI domain
% might be 
are
imposed by the specific application and consideration with respect 
to the users' expectation. Our example application aims 
to provide insightful vizualisations to the user's business. 
Thus, a user who types `revenue' as question is
not necessarily interested in the total revenue achieved by the company 
since its existence (which a query consisting only of the measure 
would return). Most likely, he is interested in a specific aspect such as 
the `revenue per year' or `revenue per resort', even though
he is not yet sure, which of these aspects he would like to explore.
Therefore, our application proposes in such situations dimensions that 
form together with the measures of the user's question a valid 
structured query. Same holds true if 
the user does not mention a measure, but only a dimension as shown 
in the example in figure~\ref{fig:running-example}. In this case, the
system proposes related measures (here `revenue').
%
Another 
%related, but more 
interesting aspect is contextualization. 
A user might have a user profile, which augments the systems 
metadata (e.g. with the city the user is located in). In order to 
simplify the data exploration and return more relevant data for 
his current task, we may leverage the user profile to impose 
additional filters. In figure~\ref{fig:running-example} 
the user asks for instance for `my city'. Knowing that
there is a mapping between `Palo Alto' in the user profile and a value 
inside the data underlying the dimension `City', we may automatically 
generate a strucured query with a filter for `Palo Alto'.
%
Considering all these structural constraints and possibilities 
to augment queries with artifacts from the underlying metadata, 
it is obvious that such constraints are difficult to express and 
maintain in an imperative programming model. In 
section~\ref{sec:structural-constraints} we will present 
as one of our major contributions a declarative way to capture such 
domain or application-specific constraints to generate structured queries.\\
%
\textbf{(4) Mapping Artifacts into Structured Queries:} Once we 
have defined constraints and artifacts that shall be considered, 
such as dimensions, measures, attributes and custom variables (e.g. 
for `top 5' or `middle-aged'), they 
have to be mapped into semantic units (e.g. `basic query' 
or `range filter' as shown in figure~\ref{fig:running-example}). 
Now we have to create a new data structure that represents 
a query such that artifacts refered in the constraints are mapped 
to the respective parts of a structured query. These are usually 
\emph{projections} (i.e. measures and dimensions), \emph{selections}
 (i.e. filters) and \emph{result modifiers} (such as ordering or truncation expressions). 
Again, different query languages, domains and applications may 
impose different requirements.
%
Clearly, measures and dimensions that where recognized as `basic query'
in figure~\ref{fig:running-example} have to be included in the projections.
`Age' as dimension refered by the range filter derived 
from `middle-aged' shall not be included in the projections, 
since it would change the semantic of the query if included in 
the {\small \verb|GROUP BY|}-statement in listing~\ref{lst:structured-query-1}. 
%
In general, it is often application-specific whether 
a dimension used within a filter expression shall be mapped
to a projection.
In our case, there is a direct mapping from the query result to a 
chart. Since most traditional chart types (e.g. bar charts) support 
only 2 dimensions, we have to reduce the number of projections to a 
minimum and therefore split very complex queries into several ones, each 
showing different views on the data set. Another way of 
reducing the number of projections is to neglect projections for 
filters having only one value (e.g. as shown for `Palo Alto' in 
figure~\ref{lst:structured-query-1}) since it does not change the 
semantics of the query. \\
%
%Again, we realize that it is not straightforward to express mappings
%from recognized or proposed artifacts to a data structure 
%representing a valid query. The approach of mapping data structures 
%derived from the user's question to a data structure describing a technical 
%query in a declarative way is detailed in conjunction with our
%solution for defining structural constraints in  
%section~\ref{sec:structural-constraints}.
%
\textbf{(5) Scoring of Queries:} The previous step generates potentially 
several structured queries which then have to be ranked 
by relevance with respect to the user's question. We propose a series 
of heuristics for ranking generated queries in section~\ref{sec:scoring}.


Finally, ranked queries have to be executed. In our approach,
we generate a intermediate query model that is than serialized 
and executed on the data source. 



\begin{figure}
\centering
\includegraphics[clip=true, trim = 0cm 7.5cm 8.5cm
0.5cm,width=1.00\linewidth]{img/data-schema.pdf} \caption{Logical data model of
an example data warehouse in notation
proposed by Golfarelli et Rizzi~\cite{Golfarelli:1998:MFD:294260.294261}: two
fact tables (reservation, sales) define different measures (e.g. revenue or
reservation days).
These facts connect the different dimensions (e.g. customer and sales person). 
Dimensions are organized in hierarchies (e.g. customer, city, region, etc.) 
and may have assigned a set of attributes (e.g. age for customer).
% Multi-dimensional queries are posed in our case in a proprietary query language
% and are translated via an abstraction layer into SQL queries (which may contain
% sub-queries).
}
\label{fig:data-schema}
\vspace{-3mm}
\end{figure}

% recognize entities, predefined in some kind of background knowledge 
%  (either data or metadata of the data warehouse, or natural language rules),
%  such as \emph{top 5}, \emph{middle-aged}, \emph{customer} or \emph{my city}; 
%  \item define and execute normalizations and transformations to map the 
%  natural language input to valid expressions that can be used in the 
%  data warehouse query language $L$, e.g., to translate \emph{middle-aged} 
%  into a numerical range;
%  \item  
%\end{enumerate}



% The problem that we are interested in can be formalized as follows.
% Given a database query language $L$ and a user $u$, we define a mapping from a
% user's question $q_u$ to a set $\{\langle
% query_{i,L},rank_i\rangle\}$ of structured queries expressed in the database
% query language $L$ ordered by $(rank_i)$:
% \begin{equation}
% q_u\mapsto \left\{\left\langle query_{i,L},rank_i \right\rangle \right\}
% \label{eq:problem}
% \end{equation}
% where $rank_i\in[0,1]$.
% To illustrate the problem that we tackle, let's consider the following question:
% \begin{equation*}
% \textnormal{\emph{Top 5 middle-aged customers in my city}}
% %\label{eq:running-example}
% \end{equation*}
% This problem of translating this question into a database query is illustrated
% figure~\ref{fig:translation-process}.







%\begin{figure}
%\centering
%\includegraphics[width=8cm]{img/running-example}
%\caption{Steps to map the question~(\ref{eq:problem}) to the
%database query}
%\label{fig:running-example}
%\end{figure}
%In this figure, we have represented with boxes the successive tokens that
%satisfy some constraints, and therefore trigger translation rules.
% Some of such rules \emph{export} some of the content of the matched tokens, and
% the exported tokens may also be \emph{recomputed} before triggering the
% translation rules.
% The process is detailed below.